package com.kevin.Code.OfferReviewVersion2;

import java.util.*;

/**
 * @author Vinlee Xiao
 * @Classname OfferII_113
 * @Description 剑指 Offer II 113. 课程顺序 拓扑排序 中等难度
 * @Date 2022/1/16 10:11
 * @Version 1.0
 */
public class OfferII_113 {

    /**
     * 广度优先遍历 找到入度为零的顶点
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        //用于记录各个顶点的入度数
        int[] indegree = new int[numCourses];
        //一个顶点可能指向多个顶点
        Map<Integer, List<Integer>> vertexMap = new HashMap<Integer, List<Integer>>();
        //索引保持
        int index = 0;
        //保存最后结果数组的数组
        int[] result = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            vertexMap.putIfAbsent(i, new ArrayList<>());
        }

        //建立vertex->vertex的映射
        for (int[] prerequisite : prerequisites) {
            int from = prerequisite[1];
            int to = prerequisite[0];
            vertexMap.get(from).add(to);
            //将该节点的入度加1
            indegree[to]++;
        }

        //队列广度优先遍历
        Deque<Integer> deque = new LinkedList<>();
        //将入度为0的顶点节点放入队列中
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                deque.addLast(i);
            }
        }

        while (!deque.isEmpty()) {
            Integer vertex = deque.pollFirst();
            //将当前课程号赋值到结果数组
            result[index++] = vertex;

            for (Integer v : vertexMap.get(vertex)) {
                indegree[v]--;
                if (indegree[v] == 0) {
                    deque.addLast(v);
                }
            }
        }

        //拓扑排序是不存在环的
        //课程prequisites为空
        if (index != numCourses) {
            return new int[0];
        }

        return result;
    }

}
